Solution The recurrence relation says that hn depends on 3 previous terms in the sequence, so we use SPMl with l=3\
Let P(x):hn≤3n−1=f(n)
The basis Step
n=1,h1=1,f(1)=30=1,P(1) is Tn=2,h2=2,f(2)=31=3,P(2) is Tn=3,h3=3,f(3)=32=9,P(3) is T
Inductive Step
assume P(k−2)∧P(k−1)∧P(k) is True.
Then
hk+1=hk+hk−1+hk−2≤3k−1+3k−2+3k−3 by hypothesis =3k−3(1+3+9)=3k−3⋅13<3k−3⋅27=3k=f(k+1)
∴P(k+1) is True and ∀n⩾1,hn≤3n−1.
Exercisep350→55,1⩾4,5,7,18,19
Why Does PMI WORK? Well Ordered Principle
Every non-empty subset of Z that is bounded below has a lead element
A set is bounded below if ∃k∈Z such that k<x,∀x in the set.
Suppose P(1) is true
and P(k)→P(k+1),∀k⩾1.
Let us suppose, if possible, that there is one integer greater than 0 such that P(n) is false.
Let S={x∈Z+∣P(x) is False }=∅
By Well Ordered Principle S1 has a least element n0 and since P(1) is true, n0>1 and P(n0) is false
Thus n0−1∈Z+and n0−1<n0 so n0−1∈/S and P(n0−1) is true.
But P(n0−1)→P(n0) so P(n0) is T, contradicting statement
Thus our assumption that S=∅ leads to a contradiction. Thus S=∅ and hence P(n) is tue, ∀x⩾1
The Well Ordered Principle has other applications. Consider the following example
Example a proof that 2 is irrational
Suppose 2=ba,a,b∈Z+
Let S={x∈Z+∣x=k2, for some k∈Z+}.
S=∅ since a=b2∈S by assumption
By W.0.P.S has a least element t and t∈Z+,t=s2 for some particular s∈Z+
Consider now the number x=t2−t. We have x=t2−t=t2−Δ2=(t−Δ)2\
Now x∈Z since t2=s⋅2∈Z+
Also x=t2−t=t(2−1)>0 since 2>1, so x∈Z+
Thus x∈S. Also x=t2−t=t(2−1)<t since 2<2
Then t is not the least element of S.
Thus S=∅, and 2∈/R
Note It can be shown that
PMI is equivalent to the W.D.P. in the following sense.
We showed WOP⇒PMI by assuming WOP as an axiom of the integers
An axiom is something that we assume to be true, or a basic law from which we deduce properties of a structure
If we take P.M.I as an axiom, then it is possible to show
PMI ⇒ W.O.P.
Cardinality of Sets
Recall that in lecture 7, we briefly considered the cardinality of set
We defined the cardinality of a finite set to be ∣S∣= the number of elements in S=n where x∈Z,x⩾0.
We include 0 as a cardinality, the cardinality of the empty set ∣∅∣=0
We also asserted, that if ∣S∣=n<+∞ then the number of subsets of S is 2x ie, ∣P(s)∣=2n=2∣S∣.
We constructed the outline of a proof of this fact using the principle of Mathematical induction
We will shortly give a direct proof of ∣P(s)∣=2n\
Fist we consider cardinality of seta in a formal way
Recall
a function f:A→B is called 1−1 when f(x)=f(y)↔x=y
a function is called onto if ∀b∈B,∃a∈A such that f(a)=b.
a function that is 1−1 and onto is called a bijection between A and B
Definition the sets A and B have the same cardinality if and only if ∃a bijection between A and B.
From this most general definition we see that the cardinality of a finite set is the number of elements in the set. arbitrarily label the elements, one, two,... up ton and we get a bijection from {1,2,⋯,n} to the set in question.
If a set cannot be put into a 1−1 correspondence with {1,…,n} for any x, we say the set is infinite
Now there is more than one cardinality for an infinite set
If a set A is not finite and there is a bijection between A and Z+={1,2,⋯,n,⋯} we say A is countably infinite
A countably infinite set is also called denumerable
If a set A is finite oR countably infinite we say A is countable
Theorem I
The following conditions are equivalent
A is countable
∃ onto map from Z+to A.
∃1−1 map from A to Z+
Proof A is countable means A is finite or A is in a 1−1 correspondence with Z+
If there exists an onto map from Z+ then A is either finite or countably infinite
If there exists a 1−1 map from A into Z+ then A is either finite on countably infinite
This theorem is really a restatement of the definitions of the terms involved
If A is an infinite set, it need not be countable. If A is infinite and not countable, ie ∃no1−1 bijection of A with Z+, we say A is uncountable
Examples
Z+∪{0} is countable.
For n∈X+, define f(n)=n−1.
Then f:Z+→Z+∪{0} is 1−1 and onto
Z−={−k∣k∈Z+}is countable. Let f:Y+→Z−be defined by f(x)=−x. f is bijection.
Z is countable.
To prove this last assertion we first prove the following
Theorem 2
Theorem 2 The union of two countable sets is countable.
Proof Let A and B be countable sets
There are 3 cases to consider
A, B both finite
one of A and B is infinite
A,B both infinite
Case (1). We have already seen that of
∣A∣=n,∣B∣=m then ∣A∪B∣=∣A∣+∣B∣−∣A∩B∣<+∞
So A∪B is finite and thus countable.
Case 2) Suppose, without loss of generality that ∣A∣=n<+∞ and B is countably infinite
Let f:Z+→B be a bijection
Suppose we have listed the elements of A as a finite sequence.
A={a1,⋯,an}={g(1),…,g(n)}
where g is a bijection from {1,.,x} to A.
Define h:Z+→A∪B by
h(k)={g(k),f(k−n),1≤k≤nn+1≤k
Then h:Z+→A∪B is an onto map
We cant guarantee that it is 1−1, since A∩B may be non-empty, but onto suffices to show A∪B is countably infinite and hence countable by Theorem 1
Case 3A+B infinite.
LetAB={f(t),…,f(n)}={g(1),⋯,g(n),…}
where f,g are bijections of Z+to A and B, respectively
h is an onto map of Z+with A∪B
Hence A∪B is countable
Z is countable, since Z=(Z+∪{0})∪Z−
When a set is countably infinite we define ito cardinality to be ℵ0 (aleph zeno, aleph naught) and we write
∣Z∣=∣Z+∣=ℵ0
Lemma Any subset of a countable set is countable
Proof: If f:Z+→A is onto, then B⊆A adopt f by sending f−1(A−B) to any element of B, then the new f is an onto map of Z+onto B, use Theorem 1
There are infinite sets that are not countable The power set of Z⊤ is uncountable
Before we prove this assertion, lat us consider the power sets of finite sets and how to "count" the number of their elements
Bit strings
a bit is a single digit, either 0 or 1
A bit string of length n is a string of n fits, 0 owl, strung together
Example:10110110110000 is a bit string of length 14
Fact There are 2n bit strings of length n
Proof There are 2 choices for the first bit, 0 or 1 . For each choice, there are 2 choices for the second bit, on 22 in total. For the 3nd bit we have 2 chries fore each of the 22 choices for the first two bit, ie 23 choices fore the first 3 bits, and so on: (and so on is short hand for "proof by induction")
Let A={a1,a2,⋯,an} be a finite set For B⊆A, let xB be the bit string of length a where
the kth bit of xB={10 if if ak∈Bak∈/B
For example, xB=00⋯0n represents the empty set ∅⊆A and xB=11⋯1n represents A⊆A.
Let B∈P(A). Define f(B)=xB.
Then f:P(A)→ Bit n={ bit-strings of length n}
f is a bijection
It is 1−1 because because if two bit-strings are different, they came from different subsets and it is onto since every bit sting corresponds to a subset of A.
Thus ∣P(A)∣=∣Bitn∣=2n when ∣A∣=n<+∞
Now turn our attention to countable infinite sets
Each subset of A now is represented by a bit string of infinite length.
xA=1111⋯x∅=0000⋯
and the map f:P(A)→Bit∞ defined by the same process as before is 1−1 and onto
We show bit ∞ is not countable by contradiction
Suppose that ∣Bit∞∣=ℵ0.
Then it is possible to list all the elements of Bit
Suppose Bit∞={x1,x2,⋯,} where we
write
This scheme generates f:Z+onto k=1⋃∞Ak. and k=1⋃∞Ak is countable.
Hilbert Hotel
Now the rational numbers Q is the countable union of the sets Q[k,k+1] where
Q[k,k+1]={x∈Q∣k≤x≤k+1,k∈Z}
We now prove Q[0,1] is countable.
Let x∈Q[0,1], then x=qp,q,p∈Z+,q⩾p
Let An={kn,k∈Z+,k⩾n} for n∈Z+
An is countably infinite.
Q[0,1]={0}∪(n=1⋃∞An) is the countable union of countable seta.
Thus Q is countable
The real numbers, R, are uncountable and ∣R∣=∣P(Z+)∣=ℵ1sometimes C for continuum
We show this by showing ∣R∣=∣Bit∞∣
First we will show that ∣[0,1]∣=∣Bit∞∣ and then we show ∣[0,1]∣=∣R∣.
When we considered changing bases in L13 we mainly considered different bases for integers We have only used "decimal expansions" for real and rational numbers
The change of base theorem can be modified to show that every decimal expansion can be convected to a "binary expansion"
Every real number can be written in the form k⋅a=k+a,k∈Z and a∈Bit∞.
Thus, for k=0,∣[0,1]∣=∣ Bit ∞∣=ℵ1
also note ∣(0,1)∣=∣[0,1]∣
To show that ∣R∣=∣[0,1]∣ we can use a number of techniques to find a 1−1, onto map between (0,1) and R
There are a number of analytic methods using functions known to us ( or maybe not known )
Ex f(x)=cot(πx) is a 1−1 onto map form (0,1) to R.
A geometric method in to wrap the interval (0,1) into a circle and use stereographic projection.
This provides a 1−1 onto map of (0,1) with R.
Cardinalities of infinite sets is a very rich topic (and hard) which we will leave for later courses
For further details read §2.5 of the text, to get an idea of the history of these results
Theorem Let A be uncountable and B be countable, B⊆A
then A\B is uncountable.
Proof Assume A\B is countable
Then A=(A\B)∪B is the union of two countable sets and hence countable
Therefore A is countable, a contradiction